package com.jzoffer;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*
* 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
* */
public class SymmetricalTree {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(2);
        TreeNode t5 = new TreeNode(3);
        t1.left = t2;
        t2.right = t3;
        t1.right = t4;
        t4.left = t5;
        System.out.println(isSymmetrical(t1));
        System.out.println(isSymmetrica2(t1));
        System.out.println(isSymmetrica3(t1));
    }

    public static boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }
        return isSubymmetrical(pRoot.left, pRoot.right);

    }

    private static boolean isSubymmetrical(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val == right.val) {
            return isSubymmetrical(left.left, right.right) && isSubymmetrical(left.right, right.left);
        }
        return false;
    }

    // 非递归1 使用DFS
    public static boolean isSymmetrica2(TreeNode pRoot) {
        /*
        * * DFS使用stack来保存成对的节点
* 1.出栈的时候也是成对成对的 ，
1.若都为空，继续；
2.一个为空，返回false;
3.不为空，比较当前值，值不等，返回false；
* 2.确定入栈顺序，每次入栈都是成对成对的，如left.left， right.right ;left.rigth,right.left
        * */
        if (pRoot == null){
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(pRoot.left);
        stack.push(pRoot.right);
        while (!stack.isEmpty()){
            TreeNode rightNode = stack.pop();
            TreeNode leftNode = stack.pop();
            if(leftNode == null && rightNode == null){
                continue;
            }
            if(leftNode == null || rightNode == null){
                return false;
            }
            if(leftNode.val != rightNode.val){
                return false;
            }
            stack.push(leftNode.left);
            stack.push(rightNode.right);
            stack.push(leftNode.right);
            stack.push(rightNode.left);
        }
        return true;
    }

    // 使用BFS
    /*
    * * BFS使用Queue来保存成对的节点，代码和上面极其相似
* 1.出队的时候也是成对成对的
1.若都为空，继续；
2.一个为空，返回false;
3.不为空，比较当前值，值不等，返回false；
* 2.确定入队顺序，每次入队都是成对成对的，如left.left， right.right ;left.rigth,right.left
    *
    * */
    public static boolean isSymmetrica3(TreeNode pRoot){
        if(pRoot == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot.left);
        queue.offer(pRoot.right);
        while (!queue.isEmpty()){
            TreeNode leftNode = queue.poll();
            TreeNode rightNode = queue.poll();
            if(leftNode  == null && rightNode == null){
                continue;
            }
            if(leftNode == null || rightNode == null){
                return false;
            }
            if(leftNode.val != rightNode.val){
                return false;
            }
            queue.offer(leftNode.left);
            queue.offer(rightNode.right);
            queue.offer(leftNode.right);
            queue.offer(rightNode.left);

        }
        return true;
     }
}
